package weekMatch.one_340;

import java.util.Arrays;

public class LeeCode_03 {
    public static void main(String[] args) {

    }
    private static int minimizeMax2(int[] nums, int p){
        Arrays.sort(nums);
        int n = nums.length, l = -1, r = nums[n - 1] - nums[0];
        while (l + 1 < r){
            int m = (l + r) / 2, cnt = 0;
            for (int i = 0; i < n - 1; i++) {
                if (nums[i + 1] - nums[i] <= m){
                    cnt++;
                    i++;
                }
            }
            if (cnt >= p){
                r = m;
            }else {
                l = m;
            }
        }
        return r;
    }

    private static int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);
        int n = nums.length, left = -1, right = nums[n - 1] - nums[0];
        while (left + 1 < right){
            int mid = (right + left) / 2, cnt = 0;
            for (int i = 0; i < n - 1; i++) {
                if (nums[i + 1] - nums[i] <= mid){
                    cnt++;
                    i++;
                }
            }
            if (cnt >= p){
                right = mid;
            }else {
                left = mid;
            }
        }
        return right;
    }
}
